#!/usr/bin/python
# -*- coding:utf-8 -*-
#鸡尾酒排序
#@author wklken@yeah.net

def cocktail_sort(l):
    print l
    size = len(l)
    sign = 1  #用于判断上轮排序是否存在数据交换
    for i in range(size/2):
        if sign:
            sign = 0
            #正向，冒泡   从   i 到    对称的位置-1
            for j in range(i,size - 1 - i):
                print "l->r  cmp",l[j],l[j+1]
                if l[j] > l[j+1]:
                    l[j], l[j+1] = l[j+1], l[j]
                    sign = 1
                    print "change", l
            #逆向，冒泡  从正向排完最大数的前一个开始，到  i
            for k in range(size- 2 - i,i,-1):
                print "r->l  cmp",l[j],l[j+1]
                if l[k] < l[k-1]:
                    l[k], l[k-1] = l[k-1], l[k]
                    sign = 1
                    print "change", l
        print l
    print l
    
    
l = [ 50,10,30,20,60,40,1]
cocktail_sort(l)